1. Field of the Invention
The present invention relates to an image processing method and apparatus for reducing the number of gradation levels of image data by performing error diffusion processing.
2. Description of the Related Art
For example, when an image with a multiple-level gradation obtained through a computer or an image input device, is outputted through an image output device such as a printer with a fewer gradation level, the number of gradation levels of the image data is required to be reduced. Pseudo halftone representation has been conventionally utilized to maintain the image quality of an original image as high as possible, while reducing the number of gradation levels. Among several methods of the pseudo halftone representation, an error diffusion method capable of producing a high-quality image has been widely used for printers with two levels of output gradation, for example. It is to be noted that the error diffusion method is a method of diffusing a quantization error caused from each of target pixels into input image data of unquantized pixels near each of target pixels.
The general principle of the error diffusion method will now be described in detail with reference to Hitoshi Takaie and Mitsuo Yae, xe2x80x98Gradation Conversion Technique of Digital Image Data with Cxe2x80x99, in Interface, August 1993, pp. 158-171.
The error diffusion method is a method to represent pseudo halftones by modulating quantization errors into high frequencies to be less perceptible considering a characteristic of human visual perception. FIG. 1 is a block diagram of an image processing apparatus for implementing typical error diffusion processing. The image processing apparatus comprises: subtracter 111 for subtracting output data of filter 114 described below from input image data x(i, j); quantizer(shown as Q) 112 for quantizing output data of the subtracter 111 and outputting the result as output image data y(i, j); subtracter 113 for subtracting output data of the subtracter 111 from output image data y(i, j); and the filter 114 for performing specific filtering processing on the output data of the subtracter 113 and outputting the result to the subtracter 111. In the drawing, a quantization error caused through quantization at the quantizer 112 is represented by e(i, j). Therefore, the output data of the subtracter 113 equals the quantization error e(i, j). Coordinates of two directions intersecting each other at right angles are represented by xe2x80x98ixe2x80x99 and xe2x80x98jxe2x80x99, respectively. The two directions will be called i direction and j direction, respectively.
The filter 114 is a sort of linear filter. The transfer function thereof is determined to be G(z1, z2). Z1 and z2 are variables in z transformation with respect to i direction and j direction, respectively. The overall configuration of the image processing apparatus shown in FIG. 1 is regarded as a two-dimensional sigma-delta modulation circuit. Therefore, the relationship of input and output in the image processing apparatus is given by expression (1) below.
Y(z1, z2)=X(z1, z2)+H(z1, z2)E(z1, z2)xe2x80x83xe2x80x83(1)
In expression (1), Y(z1, z2), X(z1, z2) and E(z1, z2) are values caused through z transformation of y(i, j), x(i, j) and e(i, j), respectively. Transfer function H(z1, Z2) of the filter for modulating quantization error E(z1, z2) is given by expression (2) below.
H(z1, z2)=1xe2x88x92G(z1, z2)xe2x80x83xe2x80x83(2)
The transfer function H(z1, z2) represents a high-pass filter of two-dimensional finite impulse response (FIR). The high-pass filter is a filter for modulating quantization errors which determines a modulation characteristic of quantization error E(z1, z2) modulated to a higher frequency. In the following description, filters represented by transfer functions H(z1, z2) and G(z1, z2) are shown as filter H(z1, z2) and filter G(z1, z2), respectively.
G(z1, z2) is given by expression (3) below.
G(z1, z2)=xcexa3xcexa3g(n1, n2)z1xe2x88x92n1z2xe2x88x92n2xe2x80x83xe2x80x83(3)
The first xcexa3 in expression (3) represents a sum when n1 is from xe2x88x92N1 to M1. The second xcexa3 in expression (3) represents a sum when n2 is from xe2x88x92N2 to M2. Each of N1, M1, N2 and M2 is a prescribed positive integer. A term g(n1, n2) represents a filter coefficient, and n1=0 and n2=0 represents a target pixel.
A coefficient of G(z1, z2), namely g(i, j), of a typical filter is given by expression (4) below, for example. The xe2x89xa0 in the expression represents a target pixel where g(0, 0)=0                              g          ⁡                      (                          i              ,              j                        )                          ⁢                                            :                        ⁡                          [                                                                                          xe2x80x83                                                                                                  xe2x80x83                                                                            *                                                        7                                                        5                                                                                        3                                                        5                                                        7                                                        5                                                        3                                                                                        1                                                        3                                                        5                                                        3                                                        1                                                              ]                                /          48                                    (        4        )            
FIG. 2 shows the frequency characteristic of a filter H(z1, z2) for modulating errors, using filter G(z1, z2) given by expression (4). FIG. 2 shows that as for frequency, the greater the absolute value is, the higher the frequency is. Filter G(z1, z2) and filter H(z1, z2) using filter G(z1, z2) given by expression (4) are called filters of Jarvis, Judice and Ninke (referred to as Jarvis"" filter in the following description).
However, performing the conventional error diffusion method as described above has a problem that in highlight area (where dots are sparse) and in shadow area (where dots are dense), a pattern called xe2x80x9cwormxe2x80x9d, characteristic of the error diffusion method, occurs, caused by the poverty of the dispersion of dots, resulting in the deterioration of the image quality.
One example of the image with the xe2x80x9cwormxe2x80x9d pattern caused by the poverty of the dispersion of dots is shown in FIG. 3. The figure shows the highlight part of the image, obtained by performing error diffusion processing using the above-mentioned common Jarvis"" filter on the image of which gradation values differ gradually in vertical direction( referred to as lamp image in vertical direction in the following description). It is obvious in the image shown in the figure that dots are dispersed unevenly, causing a row of dots such as the mark of worm creeping, xe2x80x9cwormxe2x80x9d pattern, resulting in the deterioration of the image quality.
The consideration of the reason why the dispersion of dots becomes poor by performing conventional error diffusion method will now be made, by focusing on the frequency characteristic of a filter for modulating quantization errors. The frequency characteristic of Jarvis"" filter shown in FIG. 2 is represented with contour lines in FIG. 4. The three-dimensional form(characteristic) of the frequency characteristic of the filter becomes clear by the representation. First, according to FIG. 4, it is obvious that the frequency characteristic of the filter is three-dimensionally asymmetrical, caused by a fact that the coefficient of the filter for modulating quantization errors is three-dimensionally asymmetrical as is shown in expression (4). Second, three-dimensional distortion is large, especially in the middle part of the frequency characteristic shown in FIG. 4, namely the characteristic part with respect to the low frequency band of quantization errors. Because the deterioration of the dispersion of dots is most remarkable in flat part, such as in highlight area or in shadow area, it is possible to be concluded that the three-dimensional distortion of the middle part of the frequency characteristic shown in FIG. 4, causes the three-dimensional inclination in the frequency characteristic of output image data, resulting in the deterioration of the dispersion of dots causing xe2x80x9cwormxe2x80x9d pattern.
Therefore, it is possible to be concluded that the problem of the dispersion of dots will be solved, when the characteristic with respect to the low frequency band of the filter for modulating quantization errors is improved to be more three-dimensionally symmetrical.
However, when the characteristic with respect to the low frequency band of the filter for modulating quantization errors is improved, then the distortion of the surrounding part of the frequency characteristic, namely the characteristic part with respect to the high frequency band, increases, and xe2x80x9cwormxe2x80x9d pattern occurs in halftone area. Therefore, with the filter for modulating quantization errors, it is difficult to accomplish a characteristic, which is three-dimensionally symmetrical in every frequency band.
It is an object of the invention to provide an image processing method and apparatus for maintaining an image quality while reducing the number of gradation levels of image data through performing error diffusion processing.
An image processing method comprises the steps of: quantizing input image data of each of pixels so as to convert the input image data into output image data assuming any of at least two quantization levels; selecting a weight coefficient for diffusing error, according to the gradation value of input image data of each of target pixels; and diffusing a quantization error, caused through quantization of each of target pixels in the step of quantizing, multiplied by the weight coefficient selected in the step of selecting weight coefficients, into input image data of unquantized pixels near each of target pixels.
An image processing apparatus comprises: means for quantizing input image data of each of pixels forming entire image data so as to convert the input image data into output image data having any of at least two quantization levels; means for selecting a weight coefficient for diffusing error, according to the gradation value of input image data of each of target pixels; and means for diffusing the quantization error caused through quantization of each of target pixels by the means for quantizing, multiplied by the weight coefficient selected by the means for selecting a weight coefficient, into input image data of unquantized pixels near each of target pixels.
According to the image processing method of the invention, input image data of each of pixels is quantized in the step of quantizing, and converted into output image data assuming any of at least two quantization levels. A weight coefficient for diffusing error is selected in the step of selecting a weight coefficient, according to the gradation value of input image data of each of target pixels. And the quantization errors, caused through quantization in the step of quantizing each of target pixels, multiplied by the weight coefficient obtained through selection in the step of selecting a weight coefficient, are diffused into input image data of unquantized pixels near each of target pixels.
According to the image processing apparatus of the invention, input image data of each of pixels is quantized by the means for quantizing, and converted into output image data assuming any of at least two quantization levels. A weight coefficient for diffusing error is selected by the means for selecting a weight coefficient, according to the gradation value of input image data of each of target pixels. And the quantization errors, caused through quantization by the means for quantizing each of target pixels, multiplied by the weight coefficient selected by the means for selecting a weight coefficient is multiplied, are diffused into input image data of unquantized pixels near the each of target pixels.
Other and further objects, features and advantages of the invention will appear more fully from the following description.